home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 4: GNU Archives / Linux Cubed Series 4 - GNU Archives.iso / gnu / gawk-3.000 / gawk-3 / gawk-3.0.0 / array.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-12-19  |  12.7 KB  |  508 lines
  1. /*
  2.  * array.c - routines for associative arrays.
  3.  */
  4.  
  5. /* 
  6.  * Copyright (C) 1986, 1988, 1989, 1991 - 95 the Free Software Foundation, Inc.
  7.  * 
  8.  * This file is part of GAWK, the GNU implementation of the
  9.  * AWK Programming Language.
  10.  * 
  11.  * GAWK is free software; you can redistribute it and/or modify
  12.  * it under the terms of the GNU General Public License as published by
  13.  * the Free Software Foundation; either version 2 of the License, or
  14.  * (at your option) any later version.
  15.  * 
  16.  * GAWK is distributed in the hope that it will be useful,
  17.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19.  * GNU General Public License for more details.
  20.  * 
  21.  * You should have received a copy of the GNU General Public License
  22.  * along with this program; if not, write to the Free Software
  23.  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA
  24.  */
  25.  
  26. /*
  27.  * Tree walks (``for (iggy in foo)'') and array deletions use expensive
  28.  * linear searching.  So what we do is start out with small arrays and
  29.  * grow them as needed, so that our arrays are hopefully small enough,
  30.  * most of the time, that they're pretty full and we're not looking at
  31.  * wasted space.
  32.  *
  33.  * The decision is made to grow the array if the average chain length is
  34.  * ``too big''. This is defined as the total number of entries in the table
  35.  * divided by the size of the array being greater than some constant.
  36.  */
  37.  
  38. #define AVG_CHAIN_MAX    10   /* don't want to linear search more than this */
  39.  
  40. #include "awk.h"
  41.  
  42. static NODE *assoc_find P((NODE *symbol, NODE *subs, int hash1));
  43. static void grow_table P((NODE *symbol));
  44.  
  45. /* concat_exp --- concatenate expression list into a single string */
  46.  
  47. NODE *
  48. concat_exp(tree)
  49. register NODE *tree;
  50. {
  51.     register NODE *r;
  52.     char *str;
  53.     char *s;
  54.     size_t len;
  55.     int offset;
  56.     size_t subseplen;
  57.     char *subsep;
  58.  
  59.     if (tree->type != Node_expression_list)
  60.         return force_string(tree_eval(tree));
  61.     r = force_string(tree_eval(tree->lnode));
  62.     if (tree->rnode == NULL)
  63.         return r;
  64.     subseplen = SUBSEP_node->lnode->stlen;
  65.     subsep = SUBSEP_node->lnode->stptr;
  66.     len = r->stlen + subseplen + 2;
  67.     emalloc(str, char *, len, "concat_exp");
  68.     memcpy(str, r->stptr, r->stlen+1);
  69.     s = str + r->stlen;
  70.     free_temp(r);
  71.     for (tree = tree->rnode; tree != NULL; tree = tree->rnode) {
  72.         if (subseplen == 1)
  73.             *s++ = *subsep;
  74.         else {
  75.             memcpy(s, subsep, subseplen+1);
  76.             s += subseplen;
  77.         }
  78.         r = force_string(tree_eval(tree->lnode));
  79.         len += r->stlen + subseplen;
  80.         offset = s - str;
  81.         erealloc(str, char *, len, "concat_exp");
  82.         s = str + offset;
  83.         memcpy(s, r->stptr, r->stlen+1);
  84.         s += r->stlen;
  85.         free_temp(r);
  86.     }
  87.     r = make_str_node(str, s - str, ALREADY_MALLOCED);
  88.     r->flags |= TEMP;
  89.     return r;
  90. }
  91.  
  92. /* assoc_clear --- flush all the values in symbol[] before doing a split() */
  93.  
  94. void
  95. assoc_clear(symbol)
  96. NODE *symbol;
  97. {
  98.     int i;
  99.     NODE *bucket, *next;
  100.  
  101.     if (symbol->var_array == NULL)
  102.         return;
  103.     for (i = 0; i < symbol->array_size; i++) {
  104.         for (bucket = symbol->var_array[i]; bucket != NULL; bucket = next) {
  105.             next = bucket->ahnext;
  106.             unref(bucket->ahname);
  107.             unref(bucket->ahvalue);
  108.             freenode(bucket);
  109.         }
  110.         symbol->var_array[i] = NULL;
  111.     }
  112.     free(symbol->var_array);
  113.     symbol->var_array = NULL;
  114.     symbol->array_size = symbol->table_size = 0;
  115.     symbol->flags &= ~ARRAYMAXED;
  116. }
  117.  
  118. /* hash --- calculate the hash function of the string in subs */
  119.  
  120. unsigned int
  121. hash(s, len, hsize)
  122. register const char *s;
  123. register size_t len;
  124. unsigned long hsize;
  125. {
  126.     register unsigned long h = 0;
  127.  
  128.     /*
  129.      * This is INCREDIBLY ugly, but fast.  We break the string up into
  130.      * 8 byte units.  On the first time through the loop we get the
  131.      * "leftover bytes" (strlen % 8).  On every other iteration, we
  132.      * perform 8 HASHC's so we handle all 8 bytes.  Essentially, this
  133.      * saves us 7 cmp & branch instructions.  If this routine is
  134.      * heavily used enough, it's worth the ugly coding.
  135.      *
  136.      * OZ's original sdbm hash, copied from Margo Seltzers db package.
  137.      */
  138.  
  139.     /*
  140.      * Even more speed:
  141.      * #define HASHC   h = *s++ + 65599 * h
  142.      * Because 65599 = pow(2, 6) + pow(2, 16) - 1 we multiply by shifts
  143.      */
  144. #define HASHC   htmp = (h << 6);  \
  145.         h = *s++ + htmp + (htmp << 10) - h
  146.  
  147.     unsigned long htmp;
  148.  
  149.     h = 0;
  150.  
  151. #if defined(VAXC)
  152.     /*    
  153.      * This was an implementation of "Duff's Device", but it has been
  154.      * redone, separating the switch for extra iterations from the
  155.      * loop. This is necessary because the DEC VAX-C compiler is
  156.      * STOOPID.
  157.      */
  158.     switch (len & (8 - 1)) {
  159.     case 7:        HASHC;
  160.     case 6:        HASHC;
  161.     case 5:        HASHC;
  162.     case 4:        HASHC;
  163.     case 3:        HASHC;
  164.     case 2:        HASHC;
  165.     case 1:        HASHC;
  166.     default:    break;
  167.     }
  168.  
  169.     if (len > (8 - 1)) {
  170.         register size_t loop = len >> 3;
  171.         do {
  172.             HASHC;
  173.             HASHC;
  174.             HASHC;
  175.             HASHC;
  176.             HASHC;
  177.             HASHC;
  178.             HASHC;
  179.             HASHC;
  180.         } while (--loop);
  181.     }
  182. #else /* ! VAXC */
  183.     /* "Duff's Device" for those who can handle it */
  184.     if (len > 0) {
  185.         register size_t loop = (len + 8 - 1) >> 3;
  186.  
  187.         switch (len & (8 - 1)) {
  188.         case 0:
  189.             do {    /* All fall throughs */
  190.                 HASHC;
  191.         case 7:        HASHC;
  192.         case 6:        HASHC;
  193.         case 5:        HASHC;
  194.         case 4:        HASHC;
  195.         case 3:        HASHC;
  196.         case 2:        HASHC;
  197.         case 1:        HASHC;
  198.             } while (--loop);
  199.         }
  200.     }
  201. #endif /* ! VAXC */
  202.  
  203.     if (h >= hsize)
  204.         h %= hsize;
  205.     return h;
  206. }
  207.  
  208. /* assoc_find --- locate symbol[subs] */
  209.  
  210. static NODE *                /* NULL if not found */
  211. assoc_find(symbol, subs, hash1)
  212. NODE *symbol;
  213. register NODE *subs;
  214. int hash1;
  215. {
  216.     register NODE *bucket, *prev = 0;
  217.  
  218.     for (bucket = symbol->var_array[hash1]; bucket != NULL;
  219.             bucket = bucket->ahnext) {
  220.         if (cmp_nodes(bucket->ahname, subs) == 0)
  221.             return bucket;
  222.         else
  223.             prev = bucket;    /* save previous list entry */
  224.     }
  225.     return NULL;
  226. }
  227.  
  228. /* in_array --- test whether the array element symbol[subs] exists or not */
  229.  
  230. int
  231. in_array(symbol, subs)
  232. NODE *symbol, *subs;
  233. {
  234.     register int hash1;
  235.     int ret;
  236.  
  237.     if (symbol->type == Node_param_list)
  238.         symbol = stack_ptr[symbol->param_cnt];
  239.     if ((symbol->flags & SCALAR) != 0)
  240.         fatal("attempt to use scalar as array");
  241.     if (symbol->var_array == NULL)
  242.         return 0;
  243.     subs = concat_exp(subs);    /* concat_exp returns a string node */
  244.     hash1 = hash(subs->stptr, subs->stlen, (unsigned long) symbol->array_size);
  245.     ret = (assoc_find(symbol, subs, hash1) != NULL);
  246.     free_temp(subs);
  247.     return ret;
  248. }
  249.  
  250. /*
  251.  * assoc_lookup:
  252.  * Find SYMBOL[SUBS] in the assoc array.  Install it with value "" if it
  253.  * isn't there. Returns a pointer ala get_lhs to where its value is stored.
  254.  *
  255.  * SYMBOL is the address of the node (or other pointer) being dereferenced.
  256.  * SUBS is a number or string used as the subscript. 
  257.  */
  258.  
  259. NODE **
  260. assoc_lookup(symbol, subs)
  261. NODE *symbol, *subs;
  262. {
  263.     register int hash1;
  264.     register NODE *bucket;
  265.  
  266.     (void) force_string(subs);
  267.  
  268.     if ((symbol->flags & SCALAR) != 0)
  269.         fatal("attempt to use scalar as array");
  270.  
  271.     if (symbol->var_array == NULL) {
  272.         symbol->type = Node_var_array;
  273.         symbol->array_size = symbol->table_size = 0;    /* sanity */
  274.         symbol->flags &= ~ARRAYMAXED;
  275.         grow_table(symbol);
  276.         hash1 = hash(subs->stptr, subs->stlen,
  277.                 (unsigned long) symbol->array_size);
  278.     } else {
  279.         hash1 = hash(subs->stptr, subs->stlen,
  280.                 (unsigned long) symbol->array_size);
  281.         bucket = assoc_find(symbol, subs, hash1);
  282.         if (bucket != NULL) {
  283.             free_temp(subs);
  284.             return &(bucket->ahvalue);
  285.         }
  286.     }
  287.  
  288.     /* It's not there, install it. */
  289.     if (do_lint && subs->stlen == 0)
  290.         warning("subscript of array `%s' is null string",
  291.             symbol->vname);
  292.  
  293.     /* first see if we would need to grow the array, before installing */
  294.     symbol->table_size++;
  295.     if ((symbol->flags & ARRAYMAXED) == 0
  296.         && symbol->table_size/symbol->array_size > AVG_CHAIN_MAX) {
  297.         grow_table(symbol);
  298.         /* have to recompute hash value for new size */
  299.         hash1 = hash(subs->stptr, subs->stlen,
  300.                 (unsigned long) symbol->array_size);
  301.     }
  302.  
  303.     getnode(bucket);
  304.     bucket->type = Node_ahash;
  305.     if (subs->flags & TEMP)
  306.         bucket->ahname = dupnode(subs);
  307.     else {
  308.         unsigned int saveflags = subs->flags;
  309.  
  310.         subs->flags &= ~MALLOC;
  311.         bucket->ahname = dupnode(subs);
  312.         subs->flags = saveflags;
  313.     }
  314.     free_temp(subs);
  315.  
  316.     /* array subscripts are strings */
  317.     bucket->ahname->flags &= ~NUMBER;
  318.     bucket->ahname->flags |= STRING;
  319.     bucket->ahvalue = Nnull_string;
  320.     bucket->ahnext = symbol->var_array[hash1];
  321.     symbol->var_array[hash1] = bucket;
  322.     return &(bucket->ahvalue);
  323. }
  324.  
  325. /* do_delete --- perform `delete array[s]' */
  326.  
  327. void
  328. do_delete(symbol, tree)
  329. NODE *symbol, *tree;
  330. {
  331.     register int hash1;
  332.     register NODE *bucket, *last;
  333.     NODE *subs;
  334.  
  335.     if (symbol->type == Node_param_list)
  336.         symbol = stack_ptr[symbol->param_cnt];
  337.     if (symbol->type == Node_var_array) {
  338.         if (symbol->var_array == NULL)
  339.             return;
  340.     } else
  341.         fatal("delete: illegal use of variable `%s' as array",
  342.             symbol->vname);
  343.     subs = concat_exp(tree);    /* concat_exp returns string node */
  344.     hash1 = hash(subs->stptr, subs->stlen, (unsigned long) symbol->array_size);
  345.  
  346.     last = NULL;
  347.     for (bucket = symbol->var_array[hash1]; bucket != NULL;
  348.             last = bucket, bucket = bucket->ahnext)
  349.         if (cmp_nodes(bucket->ahname, subs) == 0)
  350.             break;
  351.     free_temp(subs);
  352.     if (bucket == NULL) {
  353.         if (do_lint)
  354.             warning("delete: index `%s' not in array `%s'",
  355.                 subs->stptr, symbol->vname);
  356.         return;
  357.     }
  358.     if (last != NULL)
  359.         last->ahnext = bucket->ahnext;
  360.     else
  361.         symbol->var_array[hash1] = bucket->ahnext;
  362.     unref(bucket->ahname);
  363.     unref(bucket->ahvalue);
  364.     freenode(bucket);
  365.     symbol->table_size--;
  366.     if (symbol->table_size <= 0) {
  367.         memset(symbol->var_array, '\0',
  368.             sizeof(NODE *) * symbol->array_size);
  369.         symbol->table_size = symbol->array_size = 0;
  370.         symbol->flags &= ~ARRAYMAXED;
  371.         free((char *) symbol->var_array);
  372.         symbol->var_array = NULL;
  373.     }
  374. }
  375.  
  376. /* assoc_scan --- start a ``for (iggy in foo)'' loop */
  377.  
  378. void
  379. assoc_scan(symbol, lookat)
  380. NODE *symbol;
  381. struct search *lookat;
  382. {
  383.     lookat->sym = symbol;
  384.     lookat->idx = 0;
  385.     lookat->bucket = NULL;
  386.     lookat->retval = NULL;
  387.     if (symbol->var_array != NULL)
  388.         assoc_next(lookat);
  389. }
  390.  
  391. /* assoc_next --- actually find the next element in array */
  392.  
  393. void
  394. assoc_next(lookat)
  395. struct search *lookat;
  396. {
  397.     register NODE *symbol = lookat->sym;
  398.     
  399.     if (symbol == NULL)
  400.         fatal("null symbol in assoc_next");
  401.     if (symbol->var_array == NULL || lookat->idx > symbol->array_size) {
  402.         lookat->retval = NULL;
  403.         return;
  404.     }
  405.     /*
  406.      * This is theoretically unsafe.  The element bucket might have
  407.      * been freed if the body of the scan did a delete on the next
  408.      * element of the bucket.  The only way to do that is by array
  409.      * reference, which is unlikely.  Basically, if the user is doing
  410.      * anything other than an operation on the current element of an
  411.      * assoc array while walking through it sequentially, all bets are
  412.      * off.  (The safe way is to register all search structs on an
  413.      * array with the array, and update all of them on a delete or
  414.      * insert)
  415.      */
  416.     if (lookat->bucket != NULL) {
  417.         lookat->retval = lookat->bucket->ahname;
  418.         lookat->bucket = lookat->bucket->ahnext;
  419.         return;
  420.     }
  421.     for (; lookat->idx < symbol->array_size; lookat->idx++) {
  422.         NODE *bucket;
  423.  
  424.         if ((bucket = symbol->var_array[lookat->idx]) != NULL) {
  425.             lookat->retval = bucket->ahname;
  426.             lookat->bucket = bucket->ahnext;
  427.             lookat->idx++;
  428.             return;
  429.         }
  430.     }
  431.     lookat->retval = NULL;
  432.     lookat->bucket = NULL;
  433.     return;
  434. }
  435.  
  436. /* grow_table --- grow a hash table */
  437.  
  438. static void
  439. grow_table(symbol)
  440. NODE *symbol;
  441. {
  442.     NODE **old, **new, *chain, *next;
  443.     int i, j;
  444.     unsigned long hash1;
  445.     unsigned long oldsize, newsize;
  446.     /*
  447.      * This is an array of primes. We grow the table by an order of
  448.      * magnitude each time (not just doubling) so that growing is a
  449.      * rare operation. We expect, on average, that it won't happen
  450.      * more than twice.  The final size is also chosen to be small
  451.      * enough so that MS-DOG mallocs can handle it. When things are
  452.      * very large (> 8K), we just double more or less, instead of
  453.      * just jumping from 8K to 64K.
  454.      */
  455.     static long sizes[] = { 13, 127, 1021, 8191, 16381, 32749, 65497 };
  456.  
  457.     /* find next biggest hash size */
  458.     newsize = oldsize = symbol->array_size;
  459.     for (i = 0, j = sizeof(sizes)/sizeof(sizes[0]); i < j; i++) {
  460.         if (oldsize < sizes[i]) {
  461.             newsize = sizes[i];
  462.             break;
  463.         }
  464.     }
  465.  
  466.     if (newsize == oldsize) {    /* table already at max (!) */
  467.         symbol->flags |= ARRAYMAXED;
  468.         return;
  469.     }
  470.  
  471.     /* allocate new table */
  472.     emalloc(new, NODE **, newsize * sizeof(NODE *), "grow_table");
  473.     memset(new, '\0', newsize * sizeof(NODE *));
  474.  
  475.     /* brand new hash table, set things up and return */
  476.     if (symbol->var_array == NULL) {
  477.         symbol->table_size = 0;
  478.         goto done;
  479.     }
  480.  
  481.     /* old hash table there, move stuff to new, free old */
  482.     old = symbol->var_array;
  483.     for (i = 0; i < oldsize; i++) {
  484.         if (old[i] == NULL)
  485.             continue;
  486.  
  487.         for (chain = old[i]; chain != NULL; chain = next) {
  488.             next = chain->ahnext;
  489.             hash1 = hash(chain->ahname->stptr,
  490.                     chain->ahname->stlen, newsize);
  491.  
  492.             /* remove from old list, add to new */
  493.             chain->ahnext = new[hash1];
  494.             new[hash1] = chain;
  495.  
  496.         }
  497.     }
  498.     free(old);
  499.  
  500. done:
  501.     /*
  502.      * note that symbol->table_size does not change if an old array,
  503.      * and is explicitly set to 0 if a new one.
  504.      */
  505.     symbol->var_array = new;
  506.     symbol->array_size = newsize;
  507. }
  508.